package acm;

import testing.*;
import complementos.*;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

import complementos.Exon;

/**
 *  
 *  Clase que representa una secuencia de DNA ( ADN en espanol ) 
 *  y esta hecho para solucionar el problema ACM "Gene Assembly - 1076"
 *  http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1076 
 *  
 */

public class DNA {

	public ArrayList<Exon> exones = new ArrayList<>();
	
	/**
	 * Requisito para ordenar los exones con Collections.sort
	 * 
	 */
	
	private static Comparator<Exon> COMPARADOR = new Comparator<Exon>() {
		public int compare(Exon o1, Exon o2){
			return o1.start - o2.start;

		}
	};
	
	/**
	 * Metodo principal. Ingresa datos y arma las secuencias de exones
	 * @param args argumentos enviados desde consola
	 */
	
	public static void main(String[] args){
		DNA d = new DNA();
		d.ingresarDatos();
		int[] secuenciaFinal = d.armarSecuencia();
		
		for(int i : secuenciaFinal){
			System.out.print(i + " ");
		}
	}
	
	/**
	 * Ingresa los datos de los exones via consola
	 */
	private void ingresarDatos(){
		this.exones.clear();
		Scanner in = new Scanner( System.in ); 

		System.out.println("Ingresar numero exones");
		int numeroExones = in.nextInt();
		in.nextLine();
		
		System.out.println("Ingresar exones");
		for(int i=1; i <= numeroExones; i++){
			int inferior = in.nextInt();
			in.nextLine();

			int superior = in.nextInt();
			in.nextLine();
			
			this.exones.add(new Exon(inferior, superior, i));
		}
	}
	
	/**
	 * Arma la secuencia mas larga de exones posibles
	 * @return los indices de la secuencia mas larga de exones posibles
	 */
	private int[] armarSecuencia(){
		
		ArrayList<int[]> secuencias = new ArrayList<>();
		
		// ordenar
		Collections.sort(this.exones, COMPARADOR);
		
		int largo = this.exones.size();
		for(int i=0; i < largo; i++){
			ArrayList<Integer> sec = new ArrayList<>();
			sec.add(Integer.valueOf( this.exones.get(i).index));
			int valor = this.exones.get(i).end;
			
			for(int j = i + 1; j < largo; j++){
				// agregar si el exon precede al anterior
				if(this.exones.get(j).start > valor){
					sec.add(Integer.valueOf(this.exones.get(j).index));
					valor = this.exones.get(j).end;
				}
			}
			
			// agregar a las secuencias generadas
			int[] secTMP = new int[sec.size()];
			int ii = 0;
			for(Integer t : sec){
				secTMP[ii] = (int)t;
				ii++;
			}
			secuencias.add(secTMP);
		}
		
		int[] secuenciaFinal = new int[0];
		for( int[] secuencia : secuencias){
			if(secuencia.length > secuenciaFinal.length){
				secuenciaFinal = secuencia;
			}
		}
		
		return secuenciaFinal;
	}
	
	/**
	 * Arma la secuencia mas larga de exones posibles
	 * 
	 * @param lista lista de exones
	 * @return los indices de la secuencia mas larga de exones posibles
	 */
	
	public int[] armarSecuencia(ArrayList<Exon> lista){
		this.exones = lista;
		int[] sec = this.armarSecuencia();
		
		for(int i : sec){
			System.out.print(" " + i);
		}
		System.out.println();
		
		return sec;
	}
	

}